1. Field of the Invention
The present invention relates to a branch prediction in a computer, and more particularly, to a branch prediction suitable for a type of a computer called a super scalar processor capable of concurrent execution of multiple instructions.
2. Description of the Background Art
The use of a branch prediction table (also known as a branch target buffer) has been conventionally known as an effective method for speeding up the branching processes in a computer, and has been utilized in a commercially available computer such as the AM 29000 micro-processor of AMD corporation for example.
Such a conventional branch prediction table operates on a simple principle that, when a branch instruction is executed, the branching address and the branch target address are registered in pair into the branch prediction table, such that when the same branch instruction is fetched next time, the instruction of the appropriate branch target can be fetched at a next process timing immediately following the fetch of the branch instruction, before the actual execution of the branch instruction, according to the branch target address corresponding to the branching address of that branch instruction which is registered in the branch prediction table, so that the branch process for that branch instruction can be carried out at higher speed. The correctness of the branch target predicted according to the branch prediction table is checked at a time of actually executing the branch instruction, and when the predicted branch target is incorrect, the corrected fetching of the appropriate branch target is carried out after the actual execution of the branch instruction.
Conceptually, in order to improve the effectiveness of such a branch prediction table, it is desirable to form the branch prediction table by a full associative or a multi-way associative memory which can register the same address at an arbitrary position in the memory.
However, when this type of a memory is used in a conventional branch prediction table, there is a possibility for an occurrence of a so called multi-entry in which the identical data are registered at a plurality of positions in the memory, which can lead to a confusion in the branch prediction.
Also, recently, a type of a computer called a VLIW (Very Long instruction Word) or a super scalar processor which is capable of concurrent execution of multiple instructions has been developed. In this type of a computer, because a plurality of instructions are going to be executed concurrently, a group of instructions to be executed concurrently is collectively fetched by using an address of one instruction in the group, so that even when there is a branch instruction in the group, the address used in fetching this group of instructions itself may not necessarily indicate the address of the branch instruction in the group. For this reason, it has been impossible to achieve the proper branch prediction by simply applying the conventional branch prediction table as described above to such a super scalar processor.
Moreover, it has also been difficult for a processor of super scalar type to adopt another conventionally known method for speeding up the branching process in a computer called delayed instructions in which the executions of the instructions which are located before the branch instruction but may very well be executed after the execution of the branch instruction are delayed in advance to the process timings after the execution of the branch instruction, because the number of delayed instructions required for each branch instruction is practically too large.